package _11_整理题目._4_动态规划._跳跃游戏;

import org.junit.Test;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * https://leetcode-cn.com/problems/jump-game-ii/
 * https://www.nowcoder.com/practice/d92a70f4f42248d688b93c9e50d2e757?tpId=230&tqId=2364399&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Ftab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D230
 * https://leetcode-cn.com/problems/jump-game-ii/solution/dongtai-by-_dc-in47/
 * https://leetcode-cn.com/problems/jump-game-ii/solution/dong-tai-gui-hua-jie-fa-by-alchemist-5r/
 *
 * 二、能到最后一个位置，求最少的跳跃次数
 *
 * 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 * 假设你总是可以到达数组的最后一个位置。
 *
 * 动态规划：
 *      定义 dp[i]，代表到达下标 i 所需要的最小步数，则 dp[n-1] 为所求。
 *      递推公式，dp[i] = 1 + min( dp[j] (j<i ; j+nums[j]>=i) )
 *      边界条件，dp[0] = 0，dp[i] = 较大值 n
 *
 * 贪心算法：
 *      每次选择在可以跳跃范围内的下一次的最远距离
 *      时间 O(n)，空间 O(1)
 */
public class _02_跳跃游戏_最少步数 {

    // 动态规划 1
    public int jump1(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, n);
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {// 遍历小于 i 的 dp，可以超过位置 i 时，更新最小步数
                if (j+nums[j]>=i) {
                    dp[i] = Math.min(dp[i], 1 + dp[j]);
                }
            }
        }
        return dp[n-1];
    }

    // 动态规划 2 优化第二个 for 循环，维护一个小根堆
    public int jump2(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        PriorityQueue<int[]> pq = new PriorityQueue<>( (o1, o2)-> o1[0] - o2[0] );
        for (int i = 0; i < n; i++) {
            while (!pq.isEmpty()) {
                int[] arr = pq.peek();
                int dpMin = arr[0];// 取出最小的 dp[j]
                int jMin = arr[1];// 取出最小的 dp[j] 对应的 j
                if (jMin + nums[jMin] < i) {// 从 j 跳不到 i 及后面的位置
                    pq.poll();
                } else {
                    dp[i] = 1 + dpMin;
                    break;
                }
            }
            pq.offer(new int[]{dp[i], i});
        }
        return dp[n-1];
    }

    // 动态规划 3
    public int jump3(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, n);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= nums[i]; j++ ) {
                if (i + j >= n) {
                    return dp[n - 1];
                }
                dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
            }
        }
        return dp[n - 1];
    }

    // 贪心算法
    public int jump4(int[] nums) {
        int n = nums.length;
        int minSteps = 0; // 最少的步数
        int rightMax = 0; // 初始化最开始可以跳跃的最远位置
        int stepEnd = rightMax; // 每一步的最后位置
        for (int i = 0; i < n-1; i++) {// 遍历所有可跳跃位置，除了最后一次位置
            rightMax = Math.max(rightMax, i+nums[i]);// 更新最远位置
            // 遍历到每一步的最后一个位置时，步数加一，并更新下一步的最后位置，
            if (i == stepEnd) {
                minSteps++;
                stepEnd = rightMax;
            }

            // 打印 在位置 i 可到达的最远位置下标
//            System.out.println("position i = " + i + ", "
//                    + "rightMax = " + rightMax + ", "
//                    + "stepEnd = " + stepEnd + ", "
//                    + "minSteps = " + minSteps
//            );
        }
        return minSteps;
    }

    @Test
    public void test() {
        int[] nums = {2,3,1,1,4};
        System.out.println(jump1(nums));
        System.out.println(jump2(nums));
        System.out.println(jump3(nums));
        System.out.println(jump4(nums));
    }
}
